package com.fantaike.algorithm.heap;

/**
 * 堆：堆是计算机科学中一类特殊的数据结构的统称，堆通常可以被看做是一棵完全二叉树的数组对象（只需要父节点大于两个子节点即可）。
 * 堆的特性：
 * 1.它是完全二叉树，除了树的最后一层结点不需要是满的，其它的每一层从左到右都是满的，如果最后一层结点不
 * 是满的，那么要求左满右不满。
 * 2.它通常用数组来实现。具体方法就是将二叉树的结点按照层级顺序放入数组中，根结点在位置1，它的子结点在位置2和3，而子结点的子
 * 结点则分别在位置4,5,6和7，以此类推。如果一个结点的位置为k，则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。这样，在不
 * 使用指针的情况下，我们也可以通过计算数组的索引在树中上下移动：从a[k]向上一层，就令k等于k/2,向下一层就令k等于2k或2k+1。
 * 3.每个结点都大于等于它的两个子结点。这里要注意堆中仅仅规定了每个结点大于等于它的两个子结点，但这两个
 * 子结点的顺序并没有做规定，跟我们之前学习的二叉查找树是有区别的。
 *
 * @author jishushen
 * @create 2022-06-18 10:26
 */
public class Heap<T extends Comparable<T>> {
    //用来存储元素的数组
    private T[] imtes;
    //记录堆中元素的个数
    private int N;

    //创建容量为capacity的Heap对象
    public Heap(int capacity) {
        this.imtes = (T[]) new Comparable[capacity+1];
        this.N = 0;
    }

    //判断堆中索引i处的元素是否小于索引j处的元素
    private boolean less(int i, int j) {
        return this.imtes[i].compareTo(this.imtes[j]) < 0;
    }

    //交换堆中i索引和j索引处的值
    private void exch(int i, int j) {
        T tmp = this.imtes[i];
        this.imtes[i] = this.imtes[j];
        this.imtes[j] = tmp;
    }

    //往堆中插入一个元素
    public void insert(T t) {
        //索引0处不添加，从索引1处开始，每次插入元素到末尾
        this.imtes[++N] = t;
        //调用上浮算法进行交换位置
        swim(N);
    }

    //使用上浮算法，使索引k处的元素能在堆中处于一个正确的位置
    private void swim(int k) {
        //通过循环，不断的比较当前节点的值和父节点的值，如果发现父节点的值比当前节点的值要小，则交换位置
        while (k > 1){
            //父节点的值，比当前节点小
            if (less(k/2,k)){
                exch(k/2,k);
            }
            //
            k = k/2;
        }
    }

    //删除堆中最大的元素,并返回这个最大元素
    public T delMax() {
        //获取堆中最大元素
        T max = imtes[1];
        //交换索引1处和最大索引处的元素，让完全二叉树中最右侧的元素变为临时根节点
        exch(1,N);
        //删除最大索引处的值
        imtes[N] = null;
        //元素个数减一
        N--;
        //使用下沉算法重新排序
        sink(1);
        //返回最大值
        return max;
    }

    //使用下沉算法，使索引k处的元素能在堆中处于一个正确的位置
    private void sink(int k) {
        //通过循环不断比较当前k节点和其左节点2*k及右节点2*k+1处的较大值的元素大小，如果当前节点小则要交换位置
        while (2*k <= N){
            //获取当前节点中较大的子节点
            int max;//记录较大节点的索引
            if (2*k+1<=N){//说明右子节点，则需要找到左节点和右节点中的最大值
                max = less(2*k,2*k+1) ? 2*k+1 : 2*k;
            }else {
                //没有右子节点，左节点为最大索引
                max = 2*k;
            }
            //比较当前节点和最大索引处的值
            if (less(max,k)){
               //如果最大索引处的值，小于当前节点处的值，则结束循环
               break;
            }
            //当前节点处的值小于，最大索引处的值，则进行交换
            exch(k,max);
            //将当前节点索引重新赋值
            k = max;
        }

    }

}
